//给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。 
//
// 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。 
//
// 
//
// 示例 1： 
//
// 输入：
//  s = "barfoothefoobarman",
//  words = ["foo","bar"]
//输出：[0,9]
//解释：
//从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
//输出的顺序不重要, [9,0] 也是有效答案。
// 
//
// 示例 2： 
//
// 输入：
//  s = "wordgoodgoodgoodbestword",
//  words = ["word","good","best","word"]
//输出：[]
// 
// Related Topics 哈希表 双指针 字符串 
// 👍 321 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

//Java：串联所有单词的子串
public class P30SubstringWithConcatenationOfAllWords {

    /**
     * 思路： 先将words转为map，然后遍历s，每隔k个元素查看是否在word中，是的话存起来，不是的话下一个
     *
     * 以测试用例1为例子：s = "barfoothefoobarman"  words = ["foo","bar"] ，单词长度k = 3，
     *
     * i = 0, 验证 bar 是否在words 中，是的话继续 foot 在words中，验证两次，因为words数组元素是两个。存在map中，然后和测试用例的map的单词次数对比
     *
     * i =1,验证 arf 在words中，不在，i++
     *
     * i = 2,验证 rfo 在words中，不在，i++
     *
     * ........
     *
     * i =9,  验证 foo 是否在words 中，是的话继续 bar 在words中，验证两次，因为words数组元素是两个。存在map中，然后和测试用例的map的单词次数对比
     *
     *
     *
     * 执行用时： 118 ms , 在所有 Java 提交中击败了 55.55% 的用户 内存消耗： 40.3 MB , 在所有 Java 提交中击败了 69.33% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> findSubstring(String s, String[] words) {
            List<Integer> resultList = new ArrayList<>();   // 结果list
            if (words.length == 0) {
                return resultList;
            }
            int length = words[0].length();     //单词长度
            HashMap<String, Integer> caseMap = convertToHashMap(words);  // 测试用例转的map
            HashMap<String, Integer> nowMap = new HashMap<>();  // 当前的map

            for (int i = 0; i < (s.length() - (length * words.length) + 1); i++) {
                for (int k = 0; k < words.length; k++) {
                    int start = i + (k * length);
                    int end = start + length;
                    String str = s.substring(start, end);
                    boolean exist = check(str, caseMap, nowMap);
                    if (!exist) {
                        break;
                    }
                }
                if (!nowMap.isEmpty()) {
                    if (checkNum(caseMap, nowMap)) {
                        resultList.add(i);
                    }
                    nowMap.clear();
                }
            }
            return resultList;
        }

        private boolean checkNum(HashMap<String, Integer> caseMap, HashMap<String, Integer> nowMap) {
            if (nowMap.size() != caseMap.size()) {
                return false;
            }
            for (String str : caseMap.keySet()) {
                Integer a = nowMap.get(str);
                if (a == null) {
                    return false;
                }
                if (a.compareTo(caseMap.get(str)) != 0) {
                    return false;
                }
            }
            return true;
        }

        // words 转成 map
        private HashMap<String, Integer> convertToHashMap(String[] words) {
            HashMap<String, Integer> map = new HashMap();
            for (String s : words) {
                Integer a = map.get(s);
                a = a == null ? 0 : a + 1;
                map.put(s, a);
            }
            return map;
        }

        // 检查是否在caseMap中，如果次数大于测试用例中的，或者不存在的，返回false
        private boolean check(String s, HashMap<String, Integer> caseMap, HashMap<String, Integer> nowMap) {
            if (caseMap.containsKey(s)) {
                int a = nowMap.get(s) == null ? 0 : nowMap.get(s) + 1;
                if (a > caseMap.get(s)) {
                    nowMap.clear();
                    return false;
                }
                nowMap.put(s, a);
                return true;
            }
            if (!nowMap.isEmpty()) {
                nowMap.clear();
            }
            return false;
        }
    }


    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P30SubstringWithConcatenationOfAllWords().new Solution();
        String s = "barfoothefoobarman";
        String[] words = new String[]{"foo","bar"};
        System.out.println(solution.findSubstring(s,words));
        // TO TEST
    }

}